/*
  List: a templated class for a doubly-linked list.

  Provide basic list functions, with built-in iterator.

  Classes using this list need copy constructors and assignment operators (for
  assigning one list to another).

  Convenience macros are provided for first -> last and last -> first loops.

  Jason Hood. Public domain.
  28 to 30 November, 1997.
*/

#ifndef _list_h
#define _list_h


template <class Type>
class List;

// Hold this item, and pointers to the previous and next items.
template <class Type>
struct Node				// Node<Type>* node;
{					// Type*       item;
  Type item;				// item = node->item;
					// or
  operator Type*() { return &item; }	// item = *node;

private:
  Node<Type> *prev, *next;

  Node() : prev(this), next(this) {}		// For the base of the list
  Node(const Type& data) : item(data) {}	// For creating new items

  friend class List<Type>;
};


template <class Type>
class List
{
protected:
  Node<Type>  base;			// Serves as both head and tail
  Node<Type>* current;			// Where the list (iterator) is
  unsigned    items;			// The number of items in the list
  bool	      update_cur;		// Update current after insert?

public:
  List(bool upd = true) : current(&base), items(0), update_cur(upd) {}
  List(const List& list);
  ~List() { empty(); }

  List& operator=(const List& list);

  // Determine if the current pointer should be updated after inserting.
  void update(bool yesno = true) { update_cur = yesno; }

  // Insert a new item before or after node, and return a pointer to it. If the
  // item could not be created (out of memory), return 0.
  Type* insert(const Type& item, Node<Type>* node, bool before = false);

  // Add an item to the end of the list.
  Type* append(const Type& item)  { return insert(item, base.prev); }

  // Add an item to the start of the list.
  Type* prepend(const Type& item) { return insert(item, &base); }

  // Insert an item before or after the current item.
  Type* insert(const Type& item, bool before = false)
  {
    return insert(item, current, before);
  }

  // Remove the desired item. If it's the current, move the current pointer
  // to the next item.
  void remove(Node<Type>* node);

  // Remove the current item.
  void remove() { remove(current); }

  // Empty the list and free all memory.
  void empty();

  // Return the number of items in the list.
  unsigned count() const { return items; }

  // Return true if the list is empty.
  bool is_empty() const { return items == 0; }


  // Set the current pointer to the desired item and return it.
  // If the list is empty, return 0.
  Type* move(Node<Type>* node) { return (items) ? &(current = node)->item : 0; }
  Type* begin() 	       { return move(base.next); }
  Type* end()		       { return move(base.prev); }

  // Return the current item.
  Type* here() const { return (items) ? &current->item : 0; }

  // Return a pointer to the node associated with the current item.
  Node<Type>* node() const { return (items) ? current : 0; }

  // Return the next or previous item, updating the current pointer. If there
  // are no more items, return 0; the pointer is left at the last/first item.
  Type* next()
  {
    return (current->next != &base) ? &(current = current->next)->item : 0;
  }

  Type* prev()
  {
    return (current->prev != &base) ? &(current = current->prev)->item : 0;
  }

  // Symbolic equivalents of the above. Note that pre- and postfix operations
  // are both the same.
  Type* operator ++()	 { return next(); }
  Type* operator ++(int) { return next(); }
  Type* operator --()	 { return prev(); }
  Type* operator --(int) { return prev(); }

  // Overload operators for implicit conversions.
  operator Type*() const       { return here(); }
  operator Node<Type>*() const { return node(); }
};

#define foritems(Type, list) \
for (Type* item = list.begin(); item != 0; item = list.next())

#define foritemsreverse(Type, list) \
for (Type* item = list.end(); item != 0; item = list.prev())

#define foritemsv(Type, var, list) \
for (Type* var = list.begin(); var != 0; var = list.next())

#define foritemsreversev(Type, var, list) \
for (Type* var = list.end(); var != 0; var = list.prev())

#define foritemsd(var, list) \
for (var = list.begin(); var != 0; var = list.next())

#define foritemsreversed(var, list) \
for (var = list.end(); var != 0; var = list.next())

#include "list.cc"

#endif
